package threshold;

/**
 * @Author wujiaming
 * @Description TODO
 * @Date 2023-03-09 22:58
 * @Version 1.0
 */
public class HasPathSum {

    /**
     * 二叉树的非递归遍历算法，当取出节点时，栈顶指针已经退出。
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {

         if(root==null){return false;}

        TreeNode[] stack1 = new TreeNode[50];
        TreeNode p = root;
        int[] stack2 = new int[50];
        int top = -1,falg;
        while(p!=null || top!=-1){
            while(p!=null){
                stack1[++top] = p;
                stack2[top] = 0;
                p = p.left;
            }
            p = stack1[top];
            falg =stack2[top--];
            if(falg==0){
                stack1[++top] = p;
                stack2[top] = 1;
                p = p.right;
            }else{
                if(p.left==null && p.right==null){
                    int temp = top;int sum=p.val;
                    while(top!=-1){
                        sum +=stack1[top--].val;
                    }
                    if(sum==targetSum){
                        return true;
                    }
                    top = temp;
                }
                p = null;
            }
        }
         return false;
    }

    public static void main(String[] args) {

        HasPathSum test = new HasPathSum();
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);
        root.left=node1;root.right=node2;
        node2.left=node3;node2.right=node4;
        System.out.println(test.hasPathSum(root,12));
    }
}
